package com.dbh.alg.algorithm.hot150.滑动窗口;

/**
 * @author 董帮辉
 * @date 2025/7/20
 * <p>
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 * <p>
 * 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 * <p>
 *
 *
 * 示例 1：
 * <p>
 * 输入：target = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 * 示例 2：
 * <p>
 * 输入：target = 4, nums = [1,4,4]
 * 输出：1
 * 示例 3：
 * <p>
 * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 * 输出：0
 * <p>
 *
 * 提示：
 * <p>
 * 1 <= target <= 109
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 104
 *
 **/
public class Leetcode209_长度最小的子数组 {

    public int minSubArrayLen(int target, int[] nums) {
        // 数组长度
        int n = nums.length;

        // 初始化答案为n+1（不可能的值）
        // 这样如果没有找到符合条件的子数组，最后返回0
        int ans = n + 1;

        // s表示当前滑动窗口内元素的和
        int s = 0;

        // left是滑动窗口的左边界指针
        int left = 0;

        // 遍历数组，i作为滑动窗口的右边界指针
        for (int i = 0; i < n; i++) {
            // 将当前元素加入滑动窗口的和
            s += nums[i];
            // 当当前窗口的和大于等于target时，尝试收缩左边界
            while (s >= target) {
                // 更新答案为当前窗口长度的最小值
                ans = Math.min(ans, i - left + 1);
                // 收缩左边界，移除左边元素的值
                s -= nums[left];
                // 左边界右移，继续尝试收缩
                left++;
            }
        }
        // 如果答案没有更新，说明没有符合条件的子数组，返回0；否则返回答案
        return ans <= n ? ans : 0;
    }
}
